      BOI.21. (Interviu). Compania XYZ caut[ s[ angajeze personal pentru cele
n posturi vacante pe care le are. La ofert[ r[spund exact n persoane. Comitetul de
selecie ar avea o misiune simpl[ dac[ fiecare din solicitani i-ar fi precizat postul
pe care dorete s[-l ocupe. Dar, datorit[ unor conjuncturi financiare nefavorabile
i a unei rate de omaj crescute, toate persoanele i declar[ disponibilitatea de
ocupa orice post. Deci comitetul va trebui s[ rezolve problema de a g[si persoana
cea mai indicat[ pentru fiecare post.
Considerai c[ suntei membru al acestui comitet i vi se cere o cea mai bun[
soluie. Regula dup[ care facei asignarea fiec[rei persoane la un post va trebui s[
in[ cont de condiiile cerute de postul respectiv (studii, experien[, recomand[ri,
abilit[i psihice, etc.). Aa c[ vei fi nevoii ca - n prima faz[ - s[ chemai la
interviu pe fiecare candidat pentru a-i aprecia (folosind un anumit punctaj) capaci-
tatea sa de a ocupa un anumit post. Dup[ ce ai strns toate datele necesare (i v-ai
f[cut o impresie) despre fiecare candidat, facei o ordonare descresc[toare a
candidailor care ar putea ocupa acest post. Bineneles, ideal ar fi ca fiecare
candidat s[ ocupe postul pe care i l-ar dori; aceasta este imposibil dac[ pentru
postul respectiv candideaz[ altul care s-a dovedit mai bun. Nu uitai c[ avei o
funcie foarte nalt[ la XYZ i suntei pl[tit cu 200.000 dolari pe an, aa c[ nu
putei fi mituit. Se consider[ de aceea c[ avei interes s[ v[ protejai compania i
vei prezenta cea mai bun[ soluie de angajare din punctul ei de vedere. Propunerile
dvs. vor fi f[cute n ordine strict descresc[toare a punctajului total pe care l-ai
stabilit pentru fiecare candidat.
Exemplu: Datele de intrare sunt referitoare la capacitatea fiec[rui candidat de a
ocupa un anumit post; ele sunt date ntr-o tabel[ cu n(1n10) linii (reprezentnd
posturile) i n coloane (candidaii). Pe prima linie se afl[ un singur num[r - n, iar
pe fiecare din urm[toarele n linii sunt date recomand[rile referitoare la capacitatea
fiec[rui candidat de a ocupa postul, codificate n numere ntregi din [0,20],
separate prin cel puin un spaiu. De exemplu:
4
4  6 14 11
7  2  8  9
3 13  1  4
5  2  0 13
La ieire, poziia ocupat[ de fiecare candidat este dat[ pe cte o linie num[rat[
separat. Referitor la exemplul anterior, r[spunsul este:
1  1
2  2
3  4
4  3
================================================
      BOI.21. (Mihai B[doiu)
program Interviu;
const
        max=100;
var
        v:array[1..max,1..max] of byte;
        t:array[1..max] of byte;
        total,n:integer;
-----------------------------------------------------
procedure scrie;
begin
        writeln('Total =',total);
end;
---------------------------------------------------------
procedure approximation_algorithm2;
var
        i,j:integer;
        io,jo,so:integer;
begin
 repeat
  so:=0;
  for i:=1 to n do
    for j:=i+1 to n do
     if so<v[t[i],j]+v[t[j],i]-v[t[i],i]-v[t[j],j] then
                        begin
       so:=v[t[i],j]+v[t[j],i]-v[t[i],i]-v[t[j],j];
       io:=i; jo:=j;
                        end;
     if so<>0 then begin
        total:=total+v[t[io],jo]+v[t[jo],io]-
            v[t[io],io]-v[t[jo],jo];
        i:=t[io]; t[io]:=t[jo]; t[jo]:=i;
                   end;
 until so=0;
end;
-------------------------------------------------------
function approximation_algorithm3:boolean;
var
        i,j,k:integer;
        io,jo,ko,so:integer;
begin
   approximation_algorithm3:=true;
   repeat
     so:=0;
     for i:=1 to n do
        for j:=i+1 to n do
           for k:=i+1 to n do
             if j<>k then begin
  if so<v[t[i],j]+v[t[j],k]+v[t[k],i]-
        v[t[i],i]-v[t[j],j]-v[t[k],k] then begin
           so:=v[t[i],j]+v[t[j],k]+v[t[k],i]-            
              v[t[i],i]-v[t[j],j]-v[t[k],k];
           io:=i; jo:=j; ko:=k;
                                           end;
                          end;
   if so<>0 then begin
     total:=total+v[t[io],jo]+v[t[jo],ko]+v[t[ko],io]-
          v[t[io],io]- v[t[jo],jo]-v[t[ko],ko];
     i:=t[ko]; t[ko]:=t[jo]; t[jo]:=t[io]; t[io]:=i;
     approximation_algorithm3:=false;
                 end;
  until so=0;
end;
---------------------------------------------------------
procedure calcul;
var
        i:integer;
begin
  total:=0;
  for i:=1 to n do begin
    t[i]:=i; inc(total,v[i,i]);
                   end;
  repeat
     approximation_algorithm2;
  until approximation_algorithm3;
end;
-----------------------------------------------------
procedure load;
var
        f:text;
        i,j:integer;
begin
  assign(f,'p5.in');
  reset(f);
  while not eof(f) do begin
     readln(f,n);
     for j:=1 to n do begin
        for i:=1 to n do read(f,v[j,i]);                 
        readln(f);
                      end;
     calcul;
     scrie;
                     end;
  close(f);
end;
-----------------------------------------
begin
   load;
end.
================================================
